1. Field of the Invention
The invention relates to the field of computer systems. More specifically, the invention relates to the area of memory management.
2. Background Information
Memory addressing schemes often use a technique called paging to implement virtual memory. When using paging, the virtual address space (i.e., the address space generated by either the execution unit of a processor or by the execution unit in conjunction with a segmentation unit of a processor) is divided into fix sized blocks called pages, each of which can be mapped onto any of the physical addresses (i.e., the addresses that correspond to hardware memory locations) available on the system. In a typical computer system, a memory management unit determines and maintains, according to paging algorithm(s), the current mappings for the virtual to physical addresses using one or more page tables.
Upon receiving a virtual address from the execution unit of a processor, typical memory management units initially translate the virtual address into its corresponding physical address using the page table(s). Since the page table(s) are often stored in main memory, accessing the page tables is time consuming. To speed up the paging translations, certain computer systems store the most recently used translations in a translation look-aside buffer or TLB (a faster memory that is often located on the processor). Upon generating a virtual address requiring translation, the memory management unit first searches for the translation in the TLB before accessing the page table(s). If the translation is stored in the TLB, a TLB "hit" is said to have occurred and the TLB provides the translation. However, if the translation is not stored in the TLB, a TLB "miss" is said to have occurred and a page table walker is invoked to access the page tables and provide the translation.
A number of different techniques are used for implementing page table walkers, including: 1) hardware on the processor to access the page table(s) (referred to as a "hardware page table walker"); 2) operating system routine(s) whose execution controls the accessing of the page table(s) (referred to as a "software page table walker"); etc. In addition, a number of different techniques are used for implementing the page tables, including: 1) forward mapping page tables; 2) hash page tables; etc. Certain systems use multiple techniques for handling TLB misses. For example, one system uses a hardware page table walker to access a hash page table and a software page table walker to control the walking of forward mapping page table(s). Thus, the phrase "page table walker" is used herein to refer to any technique for providing a translation when another address translation unit cannot provide the translation.
In certain computer system, it is advantageous to simultaneously support different page sizes. A page table walker that simultaneously supports different page sizes can be implemented using any number of different schemes, including: 1) multiple page table schemes (referred to herein as "forward mapping schemes"); and 2) single page table schemes.
FIG. 1 is a block diagram illustrating an exemplary forward mapping scheme that simultaneously supports two page sizes. As shown in FIG. 1, the virtual addresses for the small pages are divided into an offset field and two index fields, while the virtual addresses for large pages are divided into a larger offset field and one index field. The contents of the first index field in each virtual address is an index into the level one page table. One or more bits are stored in each entry of the level one page table to indicate if that entry is associated with a large or small page. If the entry is associated with a small page, the entry stores the base address of a level 2 page table that must be accessed. In contrast, if the entry is associated with a large page, the entry stores the base address of the large page.
A limitation of forward mapping schemes is that they require a separate level of pages tables for each page size supported. In addition, the smaller page sizes require multiple page table entries, and therefore, multiple page table accesses. Unfortunately, the smaller page sizes are typically used more often than the larger.
In contrast, single page table schemes build a single page table that is created for the smallest supported page size. Singe page table schemes include hashed page table schemes, inverted page table schemes, etc. Each entry in the page table stores the base address of a page. Since the page table is created for the smallest supported page size, multiple page table entries must be used to identify pages of a larger page size. For example, FIG. 2 is a block diagram illustrating an exemplary single page table scheme that simultaneously supports two page sizes. As shown in FIG. 2, the virtual addresses associated with both large and small page sizes are divided into a virtual page number field and an offset field. The contents of the virtual page number field are used to identify a page, while the contents of the offset field are used to identify the different address locations in that page. For a given page, the contents of the virtual page number field for all virtual addresses mapped to that page are the same, while the contents of the offset field vary.
The contents of a page entry field in each virtual address are used to identify an entry in the page table. The contents of the page entry field can be used to directly identify an entry in the page table (e.g., concatenating the contents of the page entry field with the base address of the page table) or to indirectly identify an entry in the page table (e.g., concatenating the base address of the page table with the results of performing a hash function on the contents of the page entry field).
For a given small page, the page entry field is the same as the virtual page number, and therefore all virtual addresses being mapped to a given small page will be mapped to the same entry in the page table. As a result, only one entry in the page table is required for each small page.
Since the page table shown in FIG. 2 is created for small pages, the page entry field used for large pages must be the same size as the page entry field used for the small pages. While the page entry field for both the small and large pages is the same size, the offset field for large pages is larger than the offset field for small pages. As a result, the page entry and offset fields for large pages overlap. Since the page entry and offset fields for large pages overlap, the page entry field for all virtual addresses mapped to the same large page will not be the same (i.e., the contents of the offset field vary for different virtual address mapped to the same large page) and multiple entries in the page table are required. The greater the overlap of the offset and page entry fields, the more entries required in the page table (i.e., an overlap of 1 bit requires 2 entries, an overlap of 2 bits requires 4 entries, etc.). As shown in FIG. 2, a large page size is created by storing the same base address in the multiple page table entries associated with that page.
A limitation of both single and multiple page table schemes is that there is no savings in the number of page table entries required for mapping large pages as opposed to small pages.